import java.util.HashMap;

/**
 * @author hewei
 * @version 1.0
 * @description: 1072. 按列翻转得到最大值等行数
 * @date 2022/11/10 14:41
 */

public class MaxEqualRowsAfterFlips {

    public int maxEqualRowsAfterFlips1(int[][] matrix) {
        HashMap<String, Integer> map = new HashMap<>();
        int n = matrix[0].length;
        int ans = 0;
        for (int[] ma : matrix) {
            StringBuilder sb1 = new StringBuilder();
            StringBuilder sb2 = new StringBuilder();
            for (int i : ma) {
                if (i == 1) {
                    sb1.append(1);
                    sb2.append(0);
                } else {
                    sb1.append(0);
                    sb2.append(1);
                }
            }
            String s1 = sb1.toString();
            String s2 = sb2.toString();
            map.put(s1, map.getOrDefault(s1, 0) + 1);
            map.put(s2, map.getOrDefault(s2, 0) + 1);
            ans = Math.max(ans, Math.max(map.get(s1), map.get(s2)));
        }
        return ans;
    }

    public int maxEqualRowsAfterFlips(int[][] matrix) {
        int n = matrix[0].length;
        Trie root = new Trie();
        int ans = 0;
        for (int i = 0; i < matrix.length; i++) {
            Trie node = root;
            for (int j = 0; j < n; j++) {
                int temp = matrix[i][0] == 0 ? matrix[i][j] : (matrix[i][j] ^ 1);
                if (node.next[temp] == null) {
                    node.next[temp] = new Trie();
                }
                node = node.next[temp];
            }
            ans = Math.max(ans, ++node.end);
        }
        return ans;
    }

    class Trie {
        Trie[] next;
        int end;

        public Trie() {
            next = new Trie[2];
            end = 0;
        }
    }
}
